package cn.edu.njust.alg.leetcode;

/**
 * 创建时间：2015年6月15日 上午11:47:37 项目名称：AlgorithmExercise
 * 
 * @author Zhou Xiumin
 * @version 1.0
 * @since JDK 1.7.0_21 文件名称：Leetcode_0_t.java 类说明：
 */
public class Leetcode_221_Maximal_Square {

	public static int dfs(char[][] matrix, int i, int j) {
		int count = 1;
		lp: while (true) {
			if (i + count > matrix.length - 1
					|| j + count > matrix[i].length - 1) {
				break;
			}
			for (int k = 0; k <= count; k++) {
				if (matrix[i + count][j + k] != '1'
						|| matrix[i + k][j + count] != '1') {
					break lp;
				}
			}
			count++;
		}

		return count;
	}

	public static int maximalSquare_old(char[][] matrix) {
		int max = 0;
		for (int i = 0; i < matrix.length; i++) {
			if (max > matrix.length - i) {
				break;
			}
			for (int j = 0; j < matrix[i].length; j++) {
				if (max > matrix[i].length - j) {
					break;
				}
				if (matrix[i][j] == '1') {
					int count = dfs(matrix, i, j);
					if (max < count) {
						max = count;
					}
				}
			}
		}
		return max * max;
	}

	public static int maximalSquare(char[][] matrix) {
		if (matrix == null || matrix.length <= 0) {
			return 0;
		}
		int max = 0;
		int i, j;
		int[][] dp = new int[matrix.length][matrix[0].length];
		for (i = 0; i < matrix[0].length; i++) {
			dp[0][i] = matrix[0][i] - '0';
			max = Math.max(max, dp[0][i]);
		}
		for (i = 0; i < matrix.length; i++) {
			dp[i][0] = matrix[i][0] - '0';
			max = Math.max(max, dp[i][0]);
		}
		for (i = 1; i < matrix.length; i++) {
			for (j = 1; j < matrix[i].length; j++) {
				if (matrix[i][j] == '1') {
					dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]),
							dp[i - 1][j - 1]) + 1;
					max = Math.max(max, dp[i][j]);
				}
			}
		}
		return max * max;
	}

	public static void main(String[] args) {

	}

}
